package com.dy.排序.内排序.选择排序.树形选择排序;
/*
8个叶子结点到根接点中的关键字，每个非终端结点中的数均等于其左右孩子结点中较小的数值，
则根结点中的数即为叶子结点的最小数。在输出最小数之后，割据关系的可传递性，欲选出次小数，
仅需将叶子结点中的最小数（13）改为“最大值”，然后从该叶子接点开始，和其左（或右）兄弟的数值进行比较，
修改从叶子结点到根的路径上各结点的数，则根结点的数值即为最小值。
 */

import java.util.Arrays;
//时间复杂度 nlogn    空间复杂度 2|log2n| -1 向上
/**
 * ---------------------------------------
 * 树形选择排序 ：
 * 对于简单排序来说，主要是进行n-1趟元素的比较，每趟比较n-2次，
 * 每趟比较取出一个最小值(也可以是最大值)，逐步使列表有序。
 * 但是第一趟的比较是可以为后续的比较提供信息的，使后续的比较次数大大减少，
 * 而后续的比较又可以为更后续的比较提供信息，这样就减少了比较的次数，减少了
 * 时间复杂度。
 * <p>
 * 实现原理：
 * 第一步，首先对n个记录进行两两比较，得到较小的n/2个数再依次比较，依次类推
 * 直到得到一个最小值,这是一个构造完全二叉树的过程，根节点即为最小元素，叶子节点为列表元素。
 * 构造的此树的存储结构可以用数组表示方法，数组长度为2n-1。填充此树，比如
 * 列表元素为：49    38     65    97   76    13    27   49
 * 构造的树为：                     13
 * 38               13
 * 38       65       13       27
 * 19  38   65  97   76  13   27  49
 * 13为根结点位最小值，列表元素为叶子节点
 * <p>
 * 第二步，移走最小元素，此时可重新为数组a的第一个位置赋值为此最小值，
 * 之后如果找出次小值则可以为第二个位置赋值，......
 * <p>
 * 第三步，找出次小值，找出最小值在叶子节点的位置，从该节点开始，和其兄弟节点
 * 进行比较，修改从叶子节点到根节点的元素值，比较完毕后，根节点为次小值。
 * 第三步比较是利用了第一次比较提供的信息，因为第一步已经得到了两两比较的
 * 较小值，只要拿第一次与最小值比较的元素(即最小值的兄弟节点)与它们比较即可得最小值。
 * 即拿上述例子的76与27比较，然后27与38比较得到次小值27。
 * 重复第二和第三步，排序完成。
 * <p>
 * PS:这里把移出去的叶子节点都要重设为最大值，可对此方法进行稍微改动
 * 可传一个最大值进来，这里是整型所以用了Integer.MAX_VALUE
 */
public class TreeSort {
    public static void treeSort(int[] nums) {
        int numsSize = nums.length;
        //不满足2的幂次方需要补充
        int treeSize;
        int tree[];

        int height =new Double(Math.ceil(Math.log(numsSize)/Math.log(2))).intValue();
        int len = new Double(Math.pow(2,height)).intValue() ;
        int loadingIndex = len-1;
        treeSize = 2*len -1;
        tree = new int[treeSize];
        for (int i = loadingIndex; i <treeSize; i++) {
            if (i - len + 1 < nums.length) {
                tree[i] = nums[i - len + 1];
            }
            //当超出时填入最大值
            else{
                tree[i] = Integer.MAX_VALUE;
            }
        }
        //填充前面部分
        for(int i = loadingIndex-1;i>=0;i--){
            tree[i] = Math.min(tree[2*(i+1)],tree[2*(i+1)-1]);
        }
        //Arrays.stream(tree).forEach(System.out::println);
        int low = 0;
        int index ;

        //用于检测该位置是否被访问过，用于相同值的检测
        boolean isActive[] = new boolean[numsSize];

        while(low <numsSize){
            //display(nums);
            int min = tree[0];

            nums[low++] = min;
            index = loadingIndex;
            //找到该最小值的位置，并设为MAX_VALUE
            for(; index<loadingIndex+numsSize && tree[index]!=min || isActive[index-loadingIndex]==true;index++);
            isActive[index-loadingIndex] = true; //将其设置为已经访问过
//            System.out.println(index);
            tree[index] = Integer.MAX_VALUE;

            while(index>0){
                if(index%2==0){
                    tree[(index-1)/2] = Math.min(tree[index],tree[index-1]);
                    index = (index-1)/2;
                }

                else{
                    tree[index/2] = Math.min(tree[index],tree[index+1]);
                    index /=2;
                }

            }


        }

    }

    public static void main(String[] args) {
        int nums[] = {3, 2, 4, 9, 2,0,8,9,10,-3};
        treeSort(nums);
        display(nums);
    }
    public static void display(int[] nums){
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        System.out.println();
    }
}
